/**
 * [457] 环形数组是否存在循环
 * tips:
 * # 全正或全负，nums[i]!=0：只能朝一个方向跳，且步长大于0
 * # k>1： 循环长度大于1
 *
 * @format
 * @lc app=leetcode.cn id=457 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {boolean}
 */

// 遍历标记+快慢循环双指针
var circularArrayLoop = function (nums) {
    // 获取下标
    nums.getNextIndex = function (index) {
        index += this[index]
        index %= this.length
        if (index < 0) index = this.length + index
        return index
    }
    // 记录每个元素在第几次外层循环被遍历
    const traversed = new Array(nums.length).fill(0)
    // 慢指针：start，循环次数：count
    let [start, count] = [0, 0]
    // 外层（慢）循环
    while (start < nums.length) {
        // 循环次数 ♻️ 用于 traversed 标记
        count++
        // 确定方向
        let direction = nums[start] > 0 ? 1 : -1
        // 初始化快指针
        let now = start
        // 更新遍历标记
        traversed[now] = count
        // 内层（快）循环
        while (true) {
            // 获取下一个索引
            let next = nums.getNextIndex(now)
            // 反向跳跃
            if (nums[next] * direction < 0) break
            // 循环长度 = 1
            if (next == now) break
            // 移动快指针
            else if (traversed[next] == 0) now = next
            // 形成循环
            else if (traversed[next] == count) return true
            // 进入之前已遍历的路径
            else break
            // 更新遍历标记
            traversed[now] = count
        }
        // 移动慢指针
        while (start < nums.length) {
            start++
            if (!traversed[start]) break
        }
    }
    return false
}
// 提交结果
// Accepted
// 44/44 cases passed (59 ms)
// Your runtime beats 92.31 % of javascript submissions
// Your memory usage beats 7.69 % of javascript submissions (49.1 MB)
// debugger
// const nums = [-1, -2, -3, -4, -5, 6]
// const RESULT = circularArrayLoop(nums)
// console.log(RESULT)
// @lc code=end
